\documentclass[11pt,leqno]{article}

\usepackage[cp1250]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[polish]{babel}

\usepackage{a4wide}

\usepackage{graphicx}

\input amssym.def

\author{Katarzyna Obrycka\and Marek Chru�ciel}
\title{Computer Chess Game --- project made on LPP classes.}
\date{ Wroc�aw, \today}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}

\maketitle

\section{Introduction}
Chess is a well known game played between two players. It's basic rules knows
almost everyone, and everyone probably played chess a couple of times. If
you're not familiar with chess rules please look at \\http://en.wikipedia.org/wiki/Chess.  Our interest as informatics student were
computer chess. We tried to develop an artificial intelligence which plays
chess. We also used an ready-to-use graphical interface - XBoard.  This report
will provide you information about our work, ideas, success and failures.


\section{General idea how to play chess.}
Computer chess has been analyzed and developed for long time now. We use only
well known algorithms. The game is played between two player. Moves are taken alternately.
That's why almost every chess programm uses some kind of MiniMax algorithm
(http://en.wikipedia.org/wiki/Minimax). So does our programm. We use in general the MiniMax 
with some heuristics. One thing is remebering the whole game graph. Because of that we have to
compute the evaluation function and the move generation for particular game state only once.
The game state evaluation function is generaly based on counting pieces that are left on board.
Every single piece of it's type receives some predefined value.

\section{Game graph and algorithm}
The fifty moves rule prevents cycles :P??
For impleented it as DAG with following private fields:
\begin{enumerate}
NODE which has:
 \item game state
 \item counter tells how many nodes point to this node, it is necessary for removing
\item value - wartosc state wyliczona przez evaluation function
Node(T const& s) Constructor zeruje counter, przypisuje nowa value stanowi
%zrób wewnętrzną numerację dla noda
END NODE
 \item lista par: dzieci noda i ruchy które na nie wskazują
\item tablica haszująca do przypisywania gamestsate nodom
\item wskaźnik na roota

\end{enumerate}
private methods:
\begin{enumerate}
 \item erase(Node* n) usuwa wezel i zmniejsza licznik jego dziecoim, jak mają zero po zmniejszeniu to je też usuwa
\item Node* get(T const& v) // returns exissting node or creates a new one
\item static bool child_less(..) zwraca które dziecko ma mniejszą wartość
\item

\end{enumerate}

publiczne tak samo:
pola:
-
metody:
-Dag(T const& state) wywoluje konstruktor noda od state i zwieksza licznik roota
bool has_children(T const& state) - czy stahn ma jakies dzieci
std::list<T> get_children(T const& state) zwraca liste dzieci stanu

void expand(T const& state) rozrasta dag uzywając generateAllMoves() do stworzenia listy move_type możliwych ruchów, applyMove to make move

void update_value(T const& state) it changes(aktuazliuje) values of  node in DAG using minmax algorithm

 T const& commit(typename T::move_type const& move) // makes and returns new root and removes oldone and everything else that's useless now

typename T::move_type const& best_move(T const& state) - minmax zwraca najlepszy ruch wykorzystuje minimaksa
\section{Evaluation function}
Like mentioned we use counting pieces as base for the function. We also give some high bonus for
checking the opposite king, or the mat. Pieces standing in the middle of the board also receive some 
bonus, as they are 'better standing'.\\
Values for piece counting :\\
PAWN\_VALUE     100\\
KNIGHT\_VALUE   300\\
BISHOP\_VALUE   325\\
ROOK\_VALUE     500\\
QUEEN\_VALUE    900\\
KING\_VALUE     1000000\\

\section{Rules implmenetation}
All the basic rules are programmed. The following rules are also included - castling, en passant, promotion.

\section{Programming work, language.}
The whole work is done in C++. We used svn for easier source code managment. You can look at the project web site
http://code.google.com/p/iichess/. There is not much there but you can download the source from the svn repository.
We tried to work on-time and we had a couple of meetings to discuss current problems. I guess the choice of C++
language was a little drawback, especially as we had more experience in use of other programming languages.

Compiling: g++ -O2 *.cpp

\section{XBoard}
As graphical interface for our program we used XBoard, can be found on http://tim-mann.org/xboard.html.
Documentation about chess engine communication protocol is available on http://tim-mann.org/xboard/engine-intf.html.
We have implemented only the ``normal'' variant of chessgame for it and some of the XBoard features:
\begin{enumerate}
 \item ``Playother'' which allowes player to play opponents colour at any moment,
 \item ``Usermove''  which interrupts computer's thinking and forces move on it.
\end{enumerate}
One can start game (under linux) by: xboard -debug -fcp ./a.out
XBoard allowes to arrange two computers match. It can by achieved easily by writing: xboard -debug -fcp ./a.out -scp gnuchess -mg 10
it means that the our engine (which was compiled to a.out) will play ten matches with gnuchess with debbuging.



\section{Successes}
We devepoled a decent chess programm with a nice XBoard graphical interface. We have done all the rules, talking 
about this it takes a lot of 'if' and 'switch' instructions to make it. Our code is pretty fine, no mess, comments
included. We have also learned a lot.

\section{Failures}
First of all like in alomst every project students make on classes we have had some problems finding free time and
some motivation. We had some ideas that we did not managed to finish like - game openings, some work on performance,
use of heuristics, pondering. We spent a lot of time findings bugs, that probably could be detected eariler if we did managed 
and plan better.



\end{document}
